package LeetCode._01算法入门.day03双指针;

import org.junit.Test;

/**
 * @author 挚爱之夕
 * @date 2022-02-22 - 02 - 22 - 20:16
 * @Description 给你一个整数数组 numbers，该数组已按非递减顺序排列
 * 请你从数组中找出满足相加之和等于目标数target的两个数。
 * 返回一个数组，代表这两个数所在下标+1
 * @Version 1.0
 */
public class _167两数之和输出下标 {
    static int[] numbers = {2, 7, 11, 15};
    static int target = 9;
    //by me 双指针
    @Test
    public void solve(){
        int[] res = twoSum(numbers, target);
        System.out.println(res[0] + "\t" + res[1]);
    }
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while(left < right){
            int sum = numbers[left] + numbers[right];
            if(sum == target){
                return new int[]{(left + 1), (right + 1)};
            }else if(sum > target){
                right--;
            }else{
                left++;
            }
        }
        return null;
    }
    /*官方思路*/
    @Test
    public void solve1(){
        int[] res = twoSum1(numbers, target);
        System.out.println(res[0] + "\t" + res[1]);
    }
    //二分查找：固定一个数，找另一个数
    public int[] twoSum1(int[] numbers, int target){
        for (int i = 0; i < numbers.length; i++) {
            int num = numbers[i];
            int anotherNum = target - num;
            int left = i + 1;
            int right = numbers.length - 1;
            while(left <= right){
                int midIndex = left +((right - left) >> 1);
                int midNum = numbers[midIndex];
                if(midNum == anotherNum){
                    return new int[]{i + 1, midIndex + 1};
                }else if(midNum <anotherNum){
                    left = midIndex + 1;
                }else{
                    right = midIndex - 1;
                }
            }
        }
        return null;
    }
}
